package 图;

import 抽象数据类型.Graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author: yangwk
 * @date: 2023/4/4
 * @description:
 **/
public class 广度优先遍历 {
    public static class BreadthFirstPaths {
        private final boolean[] marked;
        private final int[] edgeTo;//从起点到一个顶点的一直路径上的最后一个顶点
        private final int s;//起点

        public BreadthFirstPaths(Graph graph, int s) {
            marked = new boolean[graph.V()];
            edgeTo = new int[graph.V()];
            this.s = s;
            bfs(graph, s);
        }

        //广度优先
        private void bfs(Graph graph, int v) {
            marked[v] = true;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(v);
            while (!queue.isEmpty()) {
                int cur = queue.poll();

                for (Integer w : graph.adj(cur)) {
                    if (!marked[w]) {
                        marked[w] = true;//标记，最短路径已知
                        edgeTo[w] = cur;//保存最短路径的最后一条边
                        queue.offer(w);
                    }
                }
            }




        }

        public boolean hasPathTo(int v) {
            return marked[v];
        }
        public Iterable<Integer> pathTo(int v) {
            if (!hasPathTo(v)) {
                return null;
            }
            Stack<Integer> path = new Stack<>();
            for (int x = v; x != s; x = edgeTo[x]) {
                path.push(x);
            }
            path.push(s);
            return path;
        }

    }
}
